The field of the invention pertains to computer generation of two-dimensional triangular meshes for finite element analyses. Triangular meshes are also used for the representation of planar surfaces for graphics, image processing and computer vision, for example. In particular, the invention pertains to improvements in triangular mesh generation to eliminate the need for human intervention to improve the shape of the mesh.
Computers have been used widely to automate the processes of design and manufacturing (Computer Aided Design and Computer Aided Manufacturing, or CAD/CAM). Engineers use CAD/CAM to create designs, to analyze the objects and to manufacture the objects. CAD/CAM is based, in part, on the use of geometric modelers which can be used to represent most engineering objects and to manipulate the parts of the objects using modeling operations which simulate design and manufacturing processes.
Geometric modelers are also used in the interface stage between design and analysis. These modelers transform the object in the design stage into the input form of the analysis stage. They do this by generating a mesh which discretizes an object into finite elements. These individual elements are analyzed using a numerical procedure which is known as the finite element method. In this method an object can be thought of as composed of a finite number of elements, each of which can be analyzed separately according to the laws of physics.
Systems of equations can be applied to the finite elements and the solutions to these equations provide an approximate solution to a class of engineering problems called boundary-value problems. Computations of most mechanical properties can be formulated as boundary-value problems. Examples include stresses, strains, deformations, velocities and reactive forces of solid structures and machine components. An important step of the finite element method is the mesh generation based on the boundary description of the object. The accuracy of the analysis depends on the quality of the generated mesh.
Since a mesh is a discrete approximation of the interior of an object, it is important that the difference between the actual object and its meshed representation be as small as possible. Until fairly recently meshes were generated manually, however, computer programs and algorithms for mesh generation have been developed to automate the mesh generation process. After mesh generation, most of these algorithms use an interative smoothing process to relocate nodes of the mesh such that elements with small angles are removed. Even with the smoothing process, none of these algorithms provide a guaranteed lower bound of the smallest angle in the mesh, and human intervention may sometimes be required to improve the mesh. Since the error in the finite element analysis is known to be inversely proportional to the smallest angle in a mesh, a guarantee on the lower bound of the smallest angle is very important for practical applications of finite element analysis.
A paper by L. Paul Chew entitled "Guaranteed-Quality Triangular Meshes" Department of Computer Science, Cornell University, Ithaca, N.Y., TR 89-983, April 1989 discloses triangular mesh generation based upon the Delaunay triangulation method and further constraining the triangulation to accommodate prespecified edges. The paper sets forth the preconditions necessary for the algorithm and a modified algorithm that substantially improves the worst case run time for the algorithm. According to the paper, the preconditions prescribe a set of data points and data edges where no two data points are closer than h (an arbitrarily selected length) and all data edges have lengths between h and the square root of three multiplied by h. The final triangulation produced by the algorithm satisfies the following additional properties. The angles in each mesh triangle are guaranteed to be between 30.degree. and 120.degree. and all edge lengths to be between h and 2h. However, the Chew algorithm does not function when the above preconditions are not satisfied.